package com.ly.algorithm.leetcode.backtracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Classname Problem77
 * @Description TODO
 * @Date 2020/12/25 15:39
 * @Author 冷心影翼
 */
public class Problem77 {

	public static void main(String[] args) {
		Solution77 solution77 = new Solution77();
		System.out.println(solution77.combine(4, 2));
	}

}


class Solution77 {

	private List<List<Integer>> res = new ArrayList<>();

	public List<List<Integer>> combine(int n, int k) {
		backTracking(1,n,k,new LinkedList<>());
		return res;
	}

	public void backTracking(int cur,int n,int k, LinkedList<Integer> path) {
		if(path.size() == k) {
			res.add(new ArrayList<>(path));
			return;
		}
		if(cur > n)
			return;
//		for (int i = 1; i <= n; i++) {
//			if(path.contains(i))
//				continue;
		path.add(cur);
		backTracking(cur+1,n,k,path);
		path.removeLast();
		backTracking(cur+1,n,k,path);
//		}
	}
}